'''
插入排序:默认把数组分为两部分,左边有序,右边无序,每次从右边取一个元素插入到左边的正确位置
时间复杂度:最优:O(n)   最坏:O(n²)
稳定性:稳定
'''


def insert_sort(list):
    n = len(list)
    for i in range(1, n):  # 从第二个数开始每次取出要插入到有序数组的数据
        idx = i
        while idx > 0:
            if list[idx] < list[idx - 1]:
                list[idx], list[idx - 1] = list[idx - 1], list[idx]
                idx -= 1
            else:
                break  # 理想情况 跳出循环


if __name__ == '__main__':
    li = [31, 65, 12, 98, 54, 21, 100, 4]
    insert_sort(li)
    print(li)
